/**
 * Dynamic Programming.
 * 
 * Let dp[i][j] represents the number of eels of length exactly 10 she can produce 
 * with the first i included elements and j cuts.
 * 
 * dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k] + tmp);
 * k is the cuts could be implemented on the i-th.
 * dp[i-1][j-k] represents the maximum number could be produced with first i-1 th elements
 * and j-k cuts. tmp is the number produced on ith element with k cuts.
 * 
 */

/**
 * @author antonio081014
 * @since Dec 28, 2011, 8:24:07 AM
 */
import java.util.Arrays;

public class Cut {
	public int getMaximum(int[] eelLengths, int maxCuts) {
		int N = eelLengths.length;
		int ret = 0;
		int[][] dp = new int[N + 1][maxCuts + 1];
		Arrays.sort(eelLengths);
		for (int i = 1; i <= N; i++) {
			int cuts = (int) ((eelLengths[i - 1] - 1) / 10);
			for (int j = 0; j <= maxCuts; j++) {
				for (int k = 0; k <= Math.min(j, cuts); k++) {
					int tmp = 0;
					if (k == 0)
						tmp = eelLengths[i - 1] == 10 ? 1 : 0;
					else if (k == cuts)
						tmp = (int) Math.floor(eelLengths[i - 1] / 10);
					else
						tmp = k;
					dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k] + tmp);
					ret = Math.max(ret, dp[i][j]);
				}
			}
		}
		return ret;
	}
	// <%:testing-code%>
}
// Powered by [KawigiEdit] 2.0!
